/*
 * Copyright (C) 2010 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.replica.replicaisland;

import java.util.Comparator;

public class ShellSorter<Type> extends Sorter<Type> {
	/**
	 * Shell sort implementation based on the one found here:
	 * http://www.augustana
	 * .ab.ca/~mohrj/courses/2004.winter/csc310/source/ShellSort.java.html Note
	 * that the running time can be tuned by adjusting the size of the increment
	 * used to pass over the array each time. Currently this function uses
	 * Robert Cruse's suggestion of increment = increment / 3 + 1.
	 */

	public void sort(Type[] array, int count, Comparator<Type> comparator) {
		int increment = count / 3 + 1;

		// Sort by insertion sort at diminishing increments.
		while (increment > 1) {
			for (int start = 0; start < increment; start++) {
				insertionSort(array, count, start, increment, comparator);
			}
			increment = increment / 3 + 1;
		}

		// Do a final pass with an increment of 1.
		// (This has to be outside the previous loop because the formula above
		// for calculating the
		// next increment will keep generating 1 repeatedly.)
		insertionSort(array, count, 0, 1, comparator);
	}

	/**
	 * Insertion sort modified to sort elements at a fixed increment apart.
	 * 
	 * The code can be revised to eliminate the initial 'if', but I found that
	 * it made the sort slower.
	 * 
	 * @param start
	 *            the start position
	 * @param increment
	 *            the increment
	 */
	public void insertionSort(Type[] array, int count, int start,
			int increment, Comparator<Type> comparator) {
		int j;
		int k;
		Type temp;

		for (int i = start + increment; i < count; i += increment) {
			j = i;
			k = j - increment;
			int delta = comparator.compare(array[j], array[k]);

			if (delta < 0) {
				// Shift all previous entries down by the current
				// increment until the proper place is found.
				temp = array[j];
				do {
					array[j] = array[k];
					j = k;
					k = j - increment;
				} while (j != start && comparator.compare(array[k], temp) > 0);
				array[j] = temp;
			}
		}
	}
}
